package ar.uba.fi.tonyvaliente.tree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;

import org.apache.commons.logging.Log;
import org.apache.commons.logging.LogFactory;

import ar.uba.fi.tonyvaliente.tree.BPlusTreeNode.AddResult;


/**
 * Representa un nodo del árbol.
 * Puede ser inner o leaf.
 * 
 * Se parametrizan los tipos de las claves y valores.
 * 
 * @author santiago
 *
 * @param <K> tipo de las claves.
 * @param <V> tipo de los valores.
 */
public class BTreeNode <K extends Comparable<K>,V> {
	
	private static Log log = LogFactory.getFactory().getInstance( BTreeNode.class );

	/**
	 * Referencia al nodo padre.
	 */
	private BReference<K, V> parent;
	
	/**
	 * Referencia al nodo, necesaria para setear como parent al hacer split
	 * y para realizar la lista de nodos a actualizar.
	 */
	private BReference<K, V> thisReference;
	
	protected BTree<K, V> tree;
	
	/**
	 * Cantidad actual de elementos en el nodo.
	 */
	protected Integer cantidadElementos;
	
	/**
	 * Máxima cantidad de elementos por nodo.
	 */
	protected Integer maxCantidadElementos;
	
	/**
	 * Lista de referencias a los nodos hijos.
	 * Van en paralelos con las claves.
	 * La referencia 0 se corresponde con el hijo izquierdo de la clave 0,
	 * la referencia 1 se corresponde con el hijo derecho de la clave 0,
	 * la referencia 1 se corresponde con el hijo izquierdo de la clave 1,
	 * La referencia 2 se corresponde con el hijo derecho de la clave 1, etc.
	 */
	private List<BReference<K, V>> references;
	
	/**
	 * Lista de claves del nodo.
	 * @see references 
	 */
	//private List<K> keys = new ArrayList<K>();
	
	/**
	 * Mapa de pares clave-valor del nodo
	 */
	private Map<K, V> datos;
	
	protected BTreeNode(BReference<K, V> parent, BTree<K, V> tree, Integer maxCantidadElementos) {
		this.parent = parent;
		this.tree = tree;
		this.datos = new TreeMap<K, V>();
		this.cantidadElementos = 0;
		this.maxCantidadElementos = maxCantidadElementos;
		this.references = new ArrayList<BReference<K,V>>();
		this.references.add(null);
	}
	
	protected BTreeNode(BReference<K, V> parent, Integer maxCantidadElementos) {
		this.parent = parent;
		this.datos = new TreeMap<K, V>();
		this.cantidadElementos = 0;
		this.maxCantidadElementos = maxCantidadElementos;
		this.references = new ArrayList<BReference<K,V>>();
		this.references.add(null);
	}
	
	protected BTreeNode(BReference<K, V> parent) {
		this.parent = parent;
	}
	
	protected BTreeNode(BTree<K, V> tree) {
		this.tree = tree;
	}
	
	protected BTreeNode( BTree<K, V> tree, Integer elementosPorNodo) {
		this.tree = tree;
		this.maxCantidadElementos = elementosPorNodo;
		this.cantidadElementos = 0;
		this.datos = new TreeMap<K, V>();
		this.references = new ArrayList<BReference<K,V>>();
		this.references.add(null);
	}
	

	
	protected BReference<K, V> getParent() {
		return parent;
	}

	protected void setParent(BReference<K, V> parent) {
		this.parent = parent;
	}

	protected Integer getCantidadElementos() {
		return cantidadElementos;
	}

	protected void setCantidadElementos(Integer cantidadElementos) {
		this.cantidadElementos = cantidadElementos;
	}

	protected Integer getMaxCantidadElementos() {
		return maxCantidadElementos;
	}

	protected void setMaxCantidadElementos(Integer maxCantidadElementos) {
		this.maxCantidadElementos = maxCantidadElementos;
	}

	protected BTree<K, V> getTree(){
		return this.tree;
	}
	
	protected void setTree(BTree<K, V> tree){
		this.tree = tree;
	}
	
	protected BReference<K, V> getThisReference() {
		return thisReference;
	}

	protected void setThisReference(BReference<K, V> thisReference) {
		this.thisReference = thisReference;
	}	
	
	/**
	 * Representa el resultado de la operación add.
	 * @author santiago
	 *
	 */
	public class AddResult<K extends Comparable<K>, V>{
		K key;
		V value;
		BReference<K, V> leftReference;
		BReference<K, V> rightReference;
		
		public K getKey() {
			return key;
		}
		public void setKey(K key) {
			this.key = key;
		}
		public BReference<K, V> getLeftReference() {
			return leftReference;
		}
		public void setLeftReference(BReference<K, V> leftReference) {
			this.leftReference = leftReference;
		}
		public BReference<K, V> getRightReference() {
			return rightReference;
		}
		public void setRightReference(BReference<K, V> rightReference) {
			this.rightReference = rightReference;
		}
		public V getValue() {
			return value;
		}
		public void setValue(V value) {
			this.value = value;
		}
		
		
	}
	
	/**
	 * Añade el par clave valor al árbol.
	 * Retorna un indicador para saber si es necesario hacer un split.
	 * 
	 * @param key
	 * @param value
	 * @return
	 */
	protected AddResult<K, V> add(K key, V value) throws BTreeException {
		log.debug("añadiendo el par: " + key + "=" + value);
		
		AddResult<K, V> result = null;
		boolean nodoModificado = false;
		
		if (datos.containsKey(key)) {
			datos.put(key, value);
			nodoModificado = true;
		} else {
			
			List<K> keys = new ArrayList<K>(this.datos.keySet());
			Collections.sort(keys);
			
			int keyIndex = getKeyIndex(key, keys);
			K clave = null;
			
			if (keyIndex < keys.size()) {
				clave = keys.get(keyIndex);
			}
			
			if (clave != null) {
				// Comparo la clave que quiero insertar con la que obtuve
				// Solo puede ser menor o mayor
				// Si es menor, tomo el hijo izquierdo; si no, tomo el derecho
				// Si no es nulo, bajo a agregar al nodo hijo
				// Si es nulo, agrego en este nodo y verifico si debo hacer split
				
				if (key.compareTo(clave) > 0) {
					keyIndex++;
				}
				
				BReference<K,V> ref = references.get(keyIndex);
				if (ref != null) {
					// Bajo a agregar
					
					BTreeNode<K,V> node = ref.getNode();
					node.setTree(this.tree);
					AddResult<K, V> resultChild = node.add(key, value);
					
					if(resultChild != null){
						
						nodoModificado = true;
						
						K resultKey = resultChild.getKey();
						int resultKeyIndex = this.getKeyIndex(resultKey, keys);
						keys.add(resultKeyIndex, resultKey);
						Collections.sort(keys);
						this.datos.put(resultKey, resultChild.getValue());
						int posicionClave = keys.indexOf(resultChild.getKey());
						references.remove(ref);
						references.add(posicionClave, resultChild.getLeftReference());
						references.add(++posicionClave, resultChild.getRightReference());
						this.cantidadElementos++;
						
						if( cantidadElementos.compareTo(maxCantidadElementos) > 0){
							//nodoModificado = false;
							nodoModificado = true;
							result = this.split();
						}
					}
					
				} else {
					// Agrego en este nodo
					datos.put(key, value);
					references.add(keyIndex, null);
					cantidadElementos++;
					nodoModificado = true;
					if (cantidadElementos > maxCantidadElementos) {
						result = this.split();
					}
				}
			} else {
				// No existe en el nodo una clave mayor a la que quiero insertar
				// Si el ultimo hijo derecho no es nulo, bajo a agregar ahi
				// Si es nulo, verifico si tengo espacio para agregar en el nodo
				// Si tengo espacio, agrego
				// Si no tengo espacio, hago un split
				
				BReference<K,V> ultimoHijoDerecho = references.get(keyIndex);
				if (ultimoHijoDerecho != null) {
					// Bajo a agregar
					AddResult<K, V> resultChild = ultimoHijoDerecho.getNode().add(key, value);
					
					if(resultChild != null){
						
						nodoModificado = true;
						
						K resultKey = resultChild.getKey();
						int resultKeyIndex = this.getKeyIndex(resultKey, keys);
						keys.add(resultKeyIndex, resultKey);
						Collections.sort(keys);
						this.datos.put(resultKey, resultChild.getValue());
						int posicionClave = keys.indexOf(resultChild.getKey());
						references.remove(ultimoHijoDerecho);
						references.add(posicionClave, resultChild.getLeftReference());
						references.add(++posicionClave, resultChild.getRightReference());
						this.cantidadElementos++;
						
						if( cantidadElementos.compareTo(maxCantidadElementos) > 0){
							//nodoModificado = false;
							nodoModificado = true;
							result = this.split();
						}
					}
				} else {
					// Agrego en este nodo
					datos.put(key, value);
					references.add(keyIndex, null);
					cantidadElementos++;
					nodoModificado = true;
					if (cantidadElementos > maxCantidadElementos) {
						result = this.split();
					}
				}
			}
		}
		
		this.getThisReference().setNode(this);
		if(nodoModificado){
			tree.getDirtyNodes().add(this.getThisReference());
		}
		
		return result;
	}

	private AddResult<K, V> split() throws BTreeException {

		// Creamos los dos nodos que van a surgir del split,
		// sus referencias y sus contenidos.
//		BReference<K, V> leftReference = this.getTree().createReference();
//		BTreeNode<K, V> leftNode = new BTreeNode<K, V>(this.getParent(), this.getTree(), this.getMaxCantidadElementos());
//		Map<K,V> leftData = new TreeMap<K, V>();
//
//		leftReference.setNode(leftNode);
//		
//		leftNode.setDatos(leftData);
		
		BReference<K, V> leftReference = this.getThisReference();
		
		
		BReference<K, V> rightReference = this.getTree().createReference();
		BTreeNode<K, V> rightNode = new BTreeNode<K, V>(this.getParent(), this.getTree(), this.getMaxCantidadElementos());
		Map<K,V> rightData = new TreeMap<K, V>();
		List<BReference<K,V>> rightReferences = new ArrayList<BReference<K,V>>();

		rightReference.setNode(rightNode);
		
		rightNode.setDatos(rightData);
		
		// Tomamos el valor medio
		int medio = this.getCantidadElementos()/2;
		
		// Pasamos las claves a una lista ordenada
		List<K> claves = new ArrayList<K>(this.datos.keySet());
		Collections.sort(claves);
		
		// Obtenemos la clave media, esta será la clave a promover
		// junto con su valor asociado
		K claveMedia = claves.get(medio);
		V valorMedio = this.datos.get(claveMedia);
		
		// Copiamos los valores a los nuevos nodos.
		int i = 0;
		for (K key : claves) {
			V value = this.datos.get(key);
			if(key.compareTo(claveMedia) >= 0){
				this.getDatos().remove(key);
				if (key.compareTo(claveMedia) > 0) {
					rightData.put(key, value);
				}
			}
			
			if (i < medio) {
				i++;
			} else {
				rightReferences.add(this.references.get(i));
				this.references.remove(i);
			}
		}
		
		// La ultima referencia que quedo en this debe ir en el nodo derecho
		// La paso al mismo y tomo la primera referencia de el para dejarla
		// como ultima de this
		int lastIndex = this.references.size()-1;
		BReference<K, V> lastThisChild = this.references.get(lastIndex);
		BReference<K, V> firstRightChild = rightReferences.get(0);
		this.references.set(lastIndex, firstRightChild);
		rightReferences.remove(0);
		rightReferences.add(lastThisChild);
		
		this.setCantidadElementos(this.getDatos().size());
		rightNode.setCantidadElementos(rightData.size());
		rightNode.setReferences(rightReferences);
		
		
		tree.getDirtyNodes().add(leftReference);
		tree.getDirtyNodes().add(rightReference);
		
		AddResult<K, V> resultado = new AddResult<K, V>();
		resultado.setLeftReference(leftReference);
		resultado.setRightReference(rightReference);
		resultado.setKey(claveMedia);
		resultado.setValue(valorMedio);
		
		return resultado;
	}
	
	/**
	 * Obtenemos la posición de la clave
	 * @param key
	 * @return
	 */
	private int getKeyIndex(K key, List<K> keys) throws BTreeException {
		
		//int keyIndex = this.keys.indexOf(key);
		int keyIndex = -1;
		
		//Collections.sort(keys);
		//keyIndex = Collections.binarySearch(keys, key);
		//log.info("keyIndex de binary search: " + keyIndex);
		
		if(keys.size() > 0){
			Iterator<K> it = keys.iterator();
			
			Boolean found = false;
			// Buscamos la primera clave mayor o igual al elemento a insertar.
			// Si todas las claves son menores devolvemos la posición
			// de la última clave.
			while (it.hasNext() && !found) {
				K clave = it.next();
				keyIndex++;
				if(clave.compareTo(key) >= 0){
					found = true;
				}
			}
		}else{
			keyIndex = 0;
		}
		return keyIndex;
	}

	/**
	 * Dada una clave devuelve su valor asociado.
	 * 
	 * @param key
	 * @return
	 */
	protected V get(K key) throws BTreeException {
		//return this.getDatos().get(key);
		V returnValue = null;
		
		if (this.datos.containsKey(key)) {
			returnValue = datos.get(key);
		} else {
			List<K> keys = new ArrayList<K>(this.datos.keySet());
			Collections.sort(keys);
			
			int keyIndex = getKeyIndex(key, keys);
			
			K clave = null;
			
			try{
				clave = keys.get(keyIndex);
			}catch(IndexOutOfBoundsException e){
				// No se hace nada, si la lista está vacia no hay clave.
				log.debug("lista de claves vacia");
			}
			
			if(clave != null){
				int compare = key.compareTo(clave); 
				if(compare < 0){
					BReference<K,V> ref = this.getReferences().get(keyIndex);
					if (ref != null) {
						returnValue = ref.getNode().get(key);
					}
				} else if (compare == 0) {
					return this.datos.get(key);
				}else{
					BReference<K,V> ref = this.getReferences().get(keyIndex + 1);
					if (ref != null) {
						returnValue = ref.getNode().get(key);
					}
				}
			}
		}
		
		return returnValue;

	}

	public Map<K, V> getDatos() {
		return datos;
	}

	protected void setDatos(Map<K, V> datos) {
		this.datos = datos;
	}

	protected List<BReference<K, V>> getReferences() {
		return references;
	}

	protected void setReferences(List<BReference<K, V>> references) {
		this.references = references;
	}

	@Override
	public String toString() {
		
		return this.datos.toString() + this.references.toString();
	}

}
